package com.demo.java.OD401_450.OD419;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【项目排期，最快完成所有工作的天数(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146259721
 */
public class OdMain {
    /**
     * 判断是否可以在最多 k 天内完成任务
     *
     * @param maxDays     每个员工最大可承担的任务总天数
     * @param tasks       任务数组
     * @param taskCount   任务数量
     * @param workerCount 员工数量
     * @return 是否能在 maxDays 内完成所有任务
     */
    private static boolean canCompleteTasks(int maxDays, int[] tasks, int taskCount, int workerCount) {
        int workersUsed = 0; // 记录使用的员工数
        int[] assigned = new int[taskCount]; // 记录任务是否被分配

        for (int i = 0; i < taskCount; i++) {
            if (assigned[i] == 1) continue; // 如果任务已经被分配，则跳过
            workersUsed++; // 增加员工数
            int currentWorkload = 0; // 记录当前员工的任务总量
            int j = i;

            while (j < taskCount) {
                if (assigned[j] == 1) {
                    j++;
                    continue;
                }
                if (tasks[j] + currentWorkload > maxDays) {
                    j++; // 任务超载，跳过
                } else {
                    currentWorkload += tasks[j]; // 分配任务
                    assigned[j] = 1;
                    j++;
                }
            }
        }
        return workersUsed <= workerCount; // 判断是否在员工数量限制内
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取任务数组
        String[] taskStrings = scanner.nextLine().split(" ");
        int taskCount = taskStrings.length;
        int[] tasks = new int[taskCount];
        for (int i = 0; i < taskCount; i++) {
            tasks[i] = Integer.parseInt(taskStrings[i]);
        }

        // 读取员工数量
        int workerCount = scanner.nextInt();

        // 对任务从大到小排序（贪心策略）
        Arrays.sort(tasks);
        for (int i = 0; i < taskCount / 2; i++) {
            int temp = tasks[i];
            tasks[i] = tasks[taskCount - i - 1];
            tasks[taskCount - i - 1] = temp;
        }

        // 二分查找确定最小的最大工期
        int left = tasks[0]; // 最小工期：最长单任务
        int right = Arrays.stream(tasks).sum() + 1; // 最大工期：所有任务加总
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canCompleteTasks(mid, tasks, taskCount, workerCount)) {
                right = mid; // 尝试更小的最大工期
            } else {
                left = mid + 1; // 需要增加最大工期
            }
        }

        // 输出最小完成天数
        System.out.println(left);
    }
}
